Communication systems typically include a plurality of stations connected to one another over a communication medium. For example, in a community antenna television (CATV) system, a headend and a plurality of subscriber stations communicate over a cable. The cable supports downstream communication from the headend to the subscriber stations and upstream communication from the subscriber stations to the headend. Data, which is transmitted between the headend and the subscriber stations, is transmitted in data frames. Accordingly, when the headend communicates with a subscriber station, the headend transmits a downstream data frame to the subscriber station, and when a subscriber station communicates with the headend, the subscriber station transmits an upstream data frame to the headend.
In such a CATV system, the headend and the subscriber stations must share the resources of the cable in some manner. For example, downstream and upstream communications are typically allocated to different frequency ranges. In a sub-split allocation, downstream communications are allocated to a frequency range between 54 MHz and 750 MHz and above, while the upstream communications are allocated to a frequency range below 42 MHz. In a mid-split allocation, downstream communications are allocated to a frequency range of 162 MHz and above, while upstream communications are allocated to a frequency range between 5 to 100 MHz. In a high-split allocation, downstream communications are allocated to a frequency range of 234 MHz and above, while upstream communications are allocated to a frequency range between 5 MHz and 174 MHz.
Moreover, the subscriber stations must also share the resources of the cable in some manner. In a time division multiple access (TDMA) CATV system, the subscriber stations typically share the cable by transmitting data during uniquely assigned and non-overlapping time periods. In a frequency division multiple access (FDMA) CATV system, the subscriber stations share the cable by dividing up the available upstream frequency bandwidth into numerous narrow frequency channels and by allocating to each subscriber station its own uniquely corresponding narrow frequency band. In a code division multiple access (CDMA) CATV system, the subscriber stations share the cable by multiplying their data messages by corresponding assigned code words and then transmitting the result.
A TDMA system, which assigns each subscriber station to a unique time slot, avoids collisions of data transmitted by the subscriber stations but restricts the amount of data throughput from the subscriber stations to the headend. An FDMA system, which allocates to each subscriber station its own uniquely corresponding narrow frequency band, similarly restricts throughput because the number of frequency bands allocated to the subscriber stations is limited. A CDMA system likewise limits throughput over a communication cable because the number of code words which are available to be assigned to subscriber stations is limited.
In order to increase throughput of the data transmitted by the subscriber stations to the headend of a CATV system, it is known to allow the subscriber stations to contend for the same frequency, time, or code word slots in the upstream data frame and to use a tree algorithm to resolve any resulting contention. Contention is created when two or more subscriber stations transmit data in the same slot or slots of an upstream data frame. When the headend detects such contention, the headend initiates a tree algorithm which assigns, for a second layer of contention, a predetermined number of resolution contention slots in the next upstream data frame for each contention slot in the previous upstream data frame in which there was contention. In other words, the tree algorithm expands each contention slot in which there was contention to a predetermined number of resolution contention slots.
Each subscriber station determines whether it transmitted in one of the contention slots in which there was contention. Each subscriber station, which determines that it transmitted in a contention slot in which there was contention, randomly selects one of the resolution contention slots corresponding to the contention slot of the previous upstream data frame in which it transmitted data. These subscriber stations then re-transmit their data in the corresponding randomly selected resolution contention slots. If the headend again detects contention, the tree algorithm assigns, for a third layer of contention, a predetermined number of resolution contention slots in the next upstream data frame for each previous resolution contention slot in the previous upstream data frame in which there was contention. The contending subscriber stations respond as before. In this way, contention is resolved.
There are several problems with this approach. For example, there is no estimation of the number of subscriber stations which transmitted colliding data so that the contention slots in which contention occurred are merely expanded to a predetermined number of resolution contention slots. Expanding the contention slots in which contention occurred to a predetermined number of resolution contention slots is not an optimum method of reducing contention because many iterations are required until all subscriber stations are able to successfully transmit their data. These iterations add excessive delay to the transmission of data, and result in excessive power being transmitted into the expanded contention slots over a long period of time which thereby saturates the communication medium and causes noise in adjacent channels.
The present invention is directed to a dynamic search tree which is used to resolve contention that arises when two or more stations of a communication system transmit in the same contention slot and which solves one or more of the above described problems.